package com.datastructure.binarytree;

/**
 * @author: 临晖
 * @date: 2023/10/21
 * @description:
 */


import jdk.nashorn.internal.ir.TernaryNode;
import sun.reflect.generics.tree.Tree;
import sun.security.x509.IssuerAlternativeNameExtension;

import java.awt.*;
import java.lang.reflect.Constructor;
import java.sql.Connection;
import java.time.chrono.IsoChronology;
import java.util.*;
import java.util.List;
import java.util.logging.Level;

/**
 * 二叉树的应用
 * 深度优先：前、中、后序遍历
 * 广度优先：层序遍历
 */
public class Solution {


    /**
     * 前序遍历
     * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        //思路一：迭代
        //ArrayList<Integer> result = new ArrayList<>();
        //if (root == null) {
        //    return result;
        //}
        //
        //Stack<TreeNode> stack = new Stack<>();
        //stack.push(root);
        //
        //while (!stack.isEmpty()) {
        //    TreeNode node = stack.pop();
        //    result.add(node.val);
        //    if (node.right != null) {
        //        stack.push(node.right);
        //    }
        //
        //    if (node.left != null) {
        //        stack.push(node.left);
        //    }
        //}
        //return result;


        //思路二：递归
        //ArrayList<Integer> result = new ArrayList<>();
        //preorder(root, result);
        //return result;

        //思路三：迭代遍历的通用遍历
        ArrayList<Integer> list = new ArrayList<>();

        if (root == null) {
            return list;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();

            if (node != null) {
                stack.pop();        //防止重复


                if (node.right != null) {
                    stack.push(node.right);
                }

                if (node.left != null) {
                    stack.push(node.left);
                }

                stack.push(node);       //前序遍历
                stack.push(null);       //添加标记
            } else {
                //这里是因为null做为标记，如果碰到空，则说明到了该弹出去的时候了
                stack.pop();

                list.add(stack.peek().val);
                stack.pop();
            }
        }

        return list;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }

        //中
        result.add(root.val);
        //左
        preorder(root.left, result);
        //右
        preorder(root.right, result);
    }


    /**
     * 中序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }

        TreeNode curr = root;
        Stack<TreeNode> stack = new Stack<>();
        while (curr != null || !stack.isEmpty()) {
            //左结点不为空就入栈
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;


                //左结点等于空的话，将中间节点加入，然后跳到右节点
                //左结点等于空的话，跳到上级中间节点
            } else {

                list.add(stack.peek().val);
                curr = stack.peek().right;
                stack.pop();
            }
        }
        return list;


        //ArrayList<Integer> list = new ArrayList<>();
        //inorder(root, list);
        //return list;
    }

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }

        //左
        inorder(root.left, list);
        //中
        list.add(root.val);
        //右
        inorder(root.right, list);
    }


    /**
     * 后续遍历
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);

            if (node.left != null) {
                stack.push(node.left);
            }

            if (node.right != null) {
                stack.push(node.right);
            }

        }

        Collections.reverse(result);
        return result;
        //递归
        //ArrayList<Integer> list = new ArrayList<>();
        //postorder(root, list);
        //return list;
    }


    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        //左
        postorder(root.left, list);
        //右
        postorder(root.right, list);
        //中
        list.add(root.val);
    }


    /**
     * 102. 二叉树的层序遍历
     * <p>
     * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        ArrayList<List<Integer>> list = new ArrayList<>();

        if (root == null) {
            return list;
        }


        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.add(root);
        while (!stack.isEmpty()) {
            int len = stack.size();


            ArrayList<Integer> array = new ArrayList<>();
            while (len > 0) {
                TreeNode node = stack.removeFirst();
                array.add(node.val);

                if (node.left != null) {
                    stack.add(node.left);
                }

                if (node.right != null) {
                    stack.add(node.right);
                }
                len--;
            }
            list.add(array);

        }
        //Collections.reverse(list);
        return list;
    }


    /**
     * 199. 二叉树的右视图
     * <p>
     * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();

        if (root == null) {
            return list;
        }

        LinkedList<TreeNode> qu = new LinkedList<>();
        qu.add(root);
        while (!qu.isEmpty()) {
            int len = qu.size();
            list.add(qu.getLast().val);
            while (len > 0) {
                TreeNode node = qu.removeFirst();

                if (node.left != null) {
                    qu.add(node.left);
                }

                if (node.right != null) {
                    qu.add(node.right);
                }
                len--;
            }
        }

        return list;
    }


    /**
     * 637. 二叉树的层平均值
     * 简单
     * 相关企业
     * 给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
     * <p>
     * <p>
     * 一遍过
     *
     * @param root
     * @return
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> list = new ArrayList<>();

        if (root == null) {
            return list;
        }

        LinkedList<TreeNode> qu = new LinkedList<>();
        qu.add(root);

        while (!qu.isEmpty()) {
            int len = qu.size();
            double count = len;
            double sum = 0;
            while (len > 0) {
                TreeNode node = qu.removeFirst();
                sum += node.val;

                if (node.left != null) {
                    qu.add(node.left);
                }

                if (node.right != null) {
                    qu.add(node.right);
                }
                len--;
            }
            list.add(sum / count);
        }

        return list;
    }


    /**
     *
     *429. N 叉树的层序遍历
     * 中等
     * 相关企业
     * 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
     * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例)
     *
     * 一遍过
     * @param root
     * @return
     */
    //public List<List<Integer>> levelOrder(Node root) {
    //    List<List<Integer>> list = new ArrayList<>();
    //
    //    if (root == null) {
    //        return list;
    //    }
    //
    //    LinkedList<Node> qu = new LinkedList<>();
    //    qu.add(root);
    //
    //    while (!qu.isEmpty()) {
    //        int len = qu.size();
    //        ArrayList<Integer> list1 = new ArrayList<>();
    //
    //        while (len > 0) {
    //            Node node = qu.removeFirst();
    //            list1.add(node.val);
    //            //int nodeSize = node.children.size();
    //            //while (nodeSize > 0) {
    //            //
    //            //}
    //            qu.addAll(node.children);
    //            len--;
    //        }
    //        list.add(list1);
    //    }
    //    return list;
    //}


    /**
     * 515. 在每个树行中找最大值
     * 中等
     * 相关企业
     * 给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
     * <p>
     * 一遍过
     *
     * @param root
     * @return
     */
    public List<Integer> largestValues(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();

        if (root == null) {
            return list;
        }

        LinkedList<TreeNode> qu = new LinkedList<>();
        qu.add(root);

        while (!qu.isEmpty()) {
            int len = qu.size();
            int max = Integer.MIN_VALUE;
            while (len > 0) {
                TreeNode node = qu.removeFirst();
                max = max > node.val ? max : node.val;

                if (node.left != null) {
                    qu.add(node.left);
                }

                if (node.right != null) {
                    qu.add(node.right);
                }
                len--;
            }
            list.add(max);
        }

        return list;
    }


    /**
     * 116. 填充每个节点的下一个右侧节点指针
     * 中等
     * 1.1K
     * 相关企业
     * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
     * <p>
     * struct Node {
     * int val;
     * Node *left;
     * Node *right;
     * Node *next;
     * }
     * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     * <p>
     * 初始状态下，所有 next 指针都被设置为 NULL。
     * <p>
     * <p>
     * 一遍过
     *
     * @param root
     * @return
     */
    public Node connect(Node root) {

        if (root == null) {
            return null;
        }

        LinkedList<Node> qu = new LinkedList<>();
        qu.add(root);

        while (!qu.isEmpty()) {
            int len = qu.size();
            while (len > 0) {
                Node node = qu.removeFirst();

                //if (node.left != null) {
                //    qu.add(node.left);
                //    node.left.next = node.right;
                //}
                //
                //if (node.right != null) {
                //    qu.add(node.right);
                //    if (len > 1) {
                //        node.right.next = qu.getFirst().left;
                //    }
                //}
                if (len > 1) {
                    node.next = qu.getFirst();
                }


                if (node.left != null) {
                    qu.add(node.left);
                }

                if (node.right != null) {
                    qu.add(node.right);
                }
                len--;
            }
        }
        return root;
    }


    /**
     * 104. 二叉树的最大深度
     * 简单
     * 1.7K
     * 相关企业
     * 给定一个二叉树 root ，返回其最大深度。
     * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
     * <p>
     * 一遍过
     *
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        //思路一:广度优先,层序遍历
        //int count = 0;
        //
        //if (root == null) {
        //    return count;
        //}
        //
        //LinkedList<TreeNode> qu = new LinkedList<>();
        //qu.add(root);
        //
        //while (!qu.isEmpty()) {
        //    int len = qu.size();
        //
        //    while (len > 0) {
        //        TreeNode node = qu.removeFirst();
        //
        //        if (node.left != null) {
        //            qu.add(node.left);
        //        }
        //
        //        if (node.right != null) {
        //            qu.add(node.right);
        //        }
        //        len--;
        //    }
        //    count++;
        //}
        //
        //return count;

        //思路二:深度优先,后续遍历
        if (root == null) {
            return 0;
        }

        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);

        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
    }


    /**
     * 111. 二叉树的最小深度
     * 简单
     * 1.1K
     * 相关企业
     * 给定一个二叉树，找出其最小深度。
     * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
     * 说明：叶子节点是指没有子节点的节点。
     * <p>
     * 俩遍过：原因，老是忘记循环递减！！！！！！！！！！！！！！！！！len--，len--。len--，len--！！！！cao
     *
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {

        //思路一：广度优先，层序遍历
        //int count = 0;
        //
        //if (root == null) {
        //    return count;
        //}
        //
        //LinkedList<TreeNode> qu = new LinkedList<>();
        //qu.add(root);
        //
        //while (!qu.isEmpty()) {
        //    int len = qu.size();
        //    count++;
        //    while (len > 0) {
        //        TreeNode node = qu.removeFirst();
        //
        //        if (node.left != null) {
        //            qu.add(node.left);
        //        }
        //
        //        if (node.right != null) {
        //            qu.add(node.right);
        //        }
        //
        //        if (node.left == null && node.right == null) {
        //            return count;
        //        }
        //    }
        //
        //}
        //return count;


        //思路二
        if (root == null) {
            return 0;
        }

        int left = minDepth(root.left);
        int right = minDepth(root.right);

        if (root.left != null && root.right == null) {
            return right + 1;
        }

        if (root.left == null && root.right != null) {
            return left + 1;
        }

        return Math.min(left, right) + 1;
    }


    /**
     * 226. 翻转二叉树
     * 简单
     * 1.7K
     * 相关企业
     * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点
     * <p>
     * 思路：使用前序或后续遍历，然后在遍历的过程中将左右子树不断反转
     *
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }

        TreeNode curr = root;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(curr);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();

            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }

            swap(node);
        }

        return root;
    }

    public void swap(TreeNode node) {
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;

    }


    /**
     * 101. 对称二叉树
     * 简单
     * 2.6K
     * 相关企业
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     * <p>
     * 思路：使用递归，或队列，将其整颗数拆分为左右俩别按顺序遍历对比
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        //思路一：递归
        //if (root == null) {
        //    return true;
        //}
        //
        //return compare(root.left, root.right);

        //思路二：迭代
        if (root == null) {
            return true;
        }
        LinkedList<TreeNode> qu = new LinkedList<>();
        qu.push(root.left);
        qu.push(root.right);

        while (!qu.isEmpty()) {
            TreeNode left = qu.removeFirst();
            TreeNode right = qu.removeFirst();

            if (left == null && right == null) {
                return true;
            } else if (left != null && right == null) {
                return false;
            } else if (left == null && right != null) {
                return false;
            } else if (left.val != right.val) {
                return false;
            }

            qu.push(left.left);
            qu.push(right.right);
            qu.push(left.right);
            qu.push(right.left);
        }

        return true;
    }


    public boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left != null && right == null) {
            return false;
        } else if (left == null && right != null) {
            return false;
        } else if (left.val != right.val) {
            return false;
        }


        return compare(left.left, right.right) && compare(left.right, right.left);

    }


    /**
     * 100. 相同的树
     * 简单
     * 1.1K
     * 相关企业
     * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {

        //思路一：层序遍历，广度优先
        //if (p == null && q == null) {
        //    return true;
        //} else if (q == null || p == null) {
        //    return false;
        //}
        //
        //LinkedList<TreeNode> qQu = new LinkedList<>();
        //LinkedList<TreeNode> pQu = new LinkedList<>();
        //
        //qQu.add(q);
        //pQu.add(p);
        //
        //while (!pQu.isEmpty() && !qQu.isEmpty()) {
        //        TreeNode node1 = qQu.removeFirst();
        //        TreeNode node2 = pQu.removeFirst();
        //
        //        if (node1.val != node2.val) {
        //            return false;
        //        } else if ((node1.left == null && node2.left != null) || (node1.left != null && node2.left == null)) {
        //            return false;
        //        } else if ((node1.right == null && node2.right != null)|| (node1.right != null && node2.right == null)) {
        //            return false;
        //        }
        //
        //
        //        if (node1.left != null) {
        //            qQu.add(node1.left);
        //        }
        //
        //        if (node1.right != null) {
        //            qQu.add(node1.right);
        //        }
        //
        //        if (node2.left != null) {
        //            pQu.add(node2.left);
        //        }
        //
        //        if (node2.right != null) {
        //            pQu.add(node2.right);
        //        }
        //
        //
        //}
        //
        //if (pQu.isEmpty() && qQu.isEmpty()) {
        //    return true;
        //} else {
        //    return false;
        //}

        //思路二:递归,深度优先
        if (p == null && q != null) {
            return false;
        } else if (p != null && q == null) {
            return false;
        } else if (p == null && q == null) {
            return true;
        } else if (p.val != q.val) {
            return false;
        }

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }


    /**
     * 572. 另一棵树的子树
     * 提示
     * 简单
     * 975
     * 相关企业
     * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
     * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
     * <p>
     * 判断子树是否相等
     *
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //三种情况,要么俩颗树相等
        //      要么是root的左子树
        //      要么是root的右子树

        if ((root == null && subRoot == null) || (root != null && subRoot == null)) {
            return true;
        } else if (root == null && subRoot != null) {
            return false;
        }

        //这里不能加这个,因为这是判断是否为一棵树的子树
        //if (root.val != subRoot.val) {
        //   return false;
        //  }

        return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }


    /**
     * 559. N 叉树的最大深度
     * 简单
     * 371
     * 相关企业
     * 给定一个 N 叉树，找到其最大深度。
     * <p>
     * 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
     * <p>
     * N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
     *
     * @param root
     * @return
     */
    public int maxDepth(Node root) {
        //广度优先:层序遍历
        //int path = 0;
        //
        //if (root == null) {
        //    return path;
        //}
        //
        //LinkedList<Node> qu = new LinkedList<>();
        //qu.add(root);
        //
        //while (!qu.isEmpty()) {
        //    int len = qu.size();
        //
        //    while (len > 0) {
        //        Node node = qu.removeFirst();
        //
        //        qu.addAll(node.children);
        //        len--;
        //    }
        //    path++;
        //}
        //return path;


        //深度优先:后续遍历

        if (root == null) {
            return 0;
        }

        ArrayList<Integer> path = new ArrayList<>();

        for (int num = 0; num < root.children.size(); num++) {
            path.add(maxDepth(root.children.get(num)));

        }
        if (path.size() == 0) {
            return 1;
        } else {
            return Collections.max(path) + 1;
        }

    }

    /**
     * 222. 完全二叉树的节点个数
     * 简单
     * 1K
     * 相关企业
     * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
     * 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
     *
     * @param root
     * @return
     */
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        LinkedList<TreeNode> qu = new LinkedList<>();

        int count = 0;
        qu.add(root);

        while (!qu.isEmpty()) {
            int len = qu.size();
            count += len;
            while (len > 0) {
                TreeNode node = qu.removeFirst();

                if (node.left != null) {
                    qu.add(node.left);
                }

                if (node.right != null) {
                    qu.add(node.right);
                }

                len--;
            }
        }

        return count;

    }


    /**
     * 110. 平衡二叉树
     * 简单
     * 1.4K
     * 相关企业
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     * <p>
     * 本题中，一棵高度平衡二叉树定义为：
     * <p>
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
     *
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        int path = getDepath(root);
        if (path != -1) {
            return true;
        } else {
            return false;
        }
    }

    public int getDepath(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int left = getDepath(node.left);
        int right = getDepath(node.right);
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        } else {
            return Math.max(left, right) + 1;
        }

    }


    /**
     * 257. 二叉树的所有路径
     * 简单
     * 1.1K
     * 相关企业
     * 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
     * <p>
     * 叶子节点 是指没有子节点的节点。
     *
     * @param root
     * @return
     */
    public static List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        ArrayList<Integer> nodes = new ArrayList<>();
        traversal(root, nodes, res);
        return res;
    }


    /**
     * @param cur
     * @param path
     * @param res
     */
    public static void traversal(TreeNode cur, String path, List<String> res) {
        path += cur.val;

        if (cur.left == null && cur.right == null) {
            res.add(path);
            return;
        }

        if (cur.left != null) {
            traversal(cur.left, path + "->", res);
        }

        if (cur.right != null) {
            traversal(cur.right, path + "->", res);
        }

    }


    public static void traversal(TreeNode cur, List<Integer> nodes, List<String> res) {
        nodes.add(cur.val);      //将当前节点加入nodes

        //判断退出递归条件
        if (cur.left == null && cur.right == null) {
            String sPath = "";
            for (int i = 0; i < nodes.size() - 1; i++) {
                sPath += (nodes.get(i) + "->");
            }

            sPath += nodes.get(nodes.size() - 1);
            res.add(sPath);
            return;
        }

        //左结点
        if (cur.left != null) {
            traversal(cur.left, nodes, res);
            //回溯
            nodes.remove(nodes.size() - 1);
        }
        //右节点

        if (cur.right != null) {
            traversal(cur.right, nodes, res);
            nodes.remove(nodes.size() - 1);
        }

    }

    /**
     * 对map进行排序
     *
     * @param map
     * @return
     */
    public List<Map.Entry<String, Integer>> mapSort(Map<String, Integer> map) {
        List<Map.Entry<String, Integer>> res = new ArrayList<>(map.entrySet());
        //根据value排序
        Collections.sort(res, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //从大到小排序
                return (o2.getValue() - o1.getValue());
            }
        });

        return res;
    }


    /**
     * 404. 左叶子之和
     * 简单
     * 671
     * 相关企业
     * 给定二叉树的根节点 root ，返回所有左叶子之和
     *
     * @param root
     * @return
     */
    public int sumOfLeftLeaves(Node root) {
        //递归退出条件
        if (root == null) {
            return 0;
        }
        //左
        int leftNum = sumOfLeftLeaves(root.left);
        if (root.left != null && root.left.left == null && root.left.right == null) {
            leftNum = root.left.val;
        }
        //右
        int rightNum = sumOfLeftLeaves(root.right);
        //中
        int sum = leftNum + rightNum;

        return sum;

    }


    /**
     * 112. 路径总和
     * 简单
     * 1.3K
     * 相关企业
     * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
     * <p>
     * 叶子节点 是指没有子节点的节点。
     *
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        return equalsSum(root, targetSum);
    }

    public boolean equalsSum(TreeNode node, int num) {

        //循环结束条件
        if (node == null) {
            return false;
        }
        //中
        if (node.left == null && node.right == null && num - node.val == 0) {
            return true;
        }

        //左右
        return equalsSum(node.left, num - node.val) || equalsSum(node.right, num - node.val);

    }


    /**
     * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
     *
     * 叶子节点 是指没有子节点的节点。
     * @param root
     * @param targetSum
     * @return
     */
    //public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    //
    //}
    //
    //private void getAllPath(TreeNode node, int targetSum, ArrayList<List<Integer>> res, ArrayList<Integer> list)  {
    //
    //}


    /**
     * 106. 从中序与后序遍历序列构造二叉树
     * 中等
     * 1.1K
     * 相关企业
     * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树
     *
     * @param inorder
     * @param postorder
     * @return
     */
    //public TreeNode buildTree(int[] inorder, int[] postorder) {
    //    //第一步，判断数组是否为空
    //    if (postorder.length == 0) {
    //        return null;
    //    }
    //
    //    //第二部，找到后续数组中的最后i一个元素
    //    int val = postorder[postorder.length - 1];
    //    TreeNode root = new TreeNode(val);
    //
    //    //叶子节点
    //    if (postorder.length == 1) {
    //        return root;
    //    }
    //
    //    //第三步，找中序数组得切割点
    //    int inIndex = 0;
    //    for (; inIndex < inorder.length; inIndex++) {
    //        if (inorder[inIndex] == val){
    //            break;
    //        }
    //    }
    //
    //
    //    //第四步，切割中序数组，得到左中序数组和右中序数组,左闭右开
    //    int[] leftInorder = Arrays.copyOfRange(inorder, 0, inIndex);
    //    int[] rightInorder = new int[]{};
    //    if (inIndex + 1 < inorder.length) {
    //        rightInorder = Arrays.copyOfRange(inorder, inIndex + 1, inorder.length);
    //    }
    //
    //    //切割后续数组
    //    int[] leftPostorder = Arrays.copyOfRange(postorder, 0, leftInorder.length);
    //    int[] rightPostorder = Arrays.copyOfRange(postorder, leftPostorder.length, postorder.length - 1);
    //
    //
    //    //切割左右子树
    //    root.left = buildTree(leftInorder, leftPostorder);
    //    root.right = buildTree(rightInorder, rightPostorder);
    //    return root;
    //
    //
    //}


    /**
     * 105. 从前序与中序遍历序列构造二叉树
     * 中等
     * 2.1K
     * 相关企业
     * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     * <p>
     * 前序：中，左，右
     * 中序：左，中，右
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public static TreeNode buildTree(int[] preorder, int[] inorder) {

        //第一，判断前序数组是否为零
        if (preorder.length == 0) {
            return null;
        }

        //第二步，找出中间值
        int val = preorder[0];
        TreeNode node = new TreeNode(val);
        //如果前序数组中，只有一个值，那么直接创建节点，然后返回
        if (preorder.length == 1) {
            return node;
        }

        //第三步，找出中序数组中得切割值
        int index = 0;
        for (; index < inorder.length; index++) {
            if (inorder[index] == val) {
                break;
            }
        }


        //第四步，切割中序数组，左中序，右中序
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, index);
        int[] rightInorder = new int[]{};
        //防止数组越界
        if (index + 1 < inorder.length) {
            rightInorder = Arrays.copyOfRange(inorder, index + 1, inorder.length);
        }

        //第五步，切割前序数组
        int[] leftPreorder = Arrays.copyOfRange(preorder, 1, 1 + leftInorder.length);
        int[] rightPreorder = Arrays.copyOfRange(preorder, 1 + leftInorder.length, preorder.length);

        //第六步，继续递归切割左右
        node.left = buildTree(leftPreorder, leftInorder);
        node.right = buildTree(rightPreorder, rightInorder);

        return node;
    }


    /**
     * 654. 最大二叉树
     * 中等
     * 742
     * 相关企业
     * 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
     * <p>
     * 创建一个根节点，其值为 nums 中的最大值。
     * 递归地在最大值 左边 的 子数组前缀上 构建左子树。
     * 递归地在最大值 右边 的 子数组后缀上 构建右子树。
     * 返回 nums 构建的 最大二叉树
     *
     * @param nums
     * @return
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        //第一步：如果nums为空，返回null
        if (nums.length == 0) {
            return null;
        }

        //第二部，找出最大值
        TreeNode node = null;
        if (nums.length == 1) {
            node = new TreeNode(nums[0]);
            return node;
        }

        //否则
        int max = Integer.MIN_VALUE;
        int maxIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            if (max < nums[i]) {
                max = nums[i];
                maxIndex = i;
            }
        }

        node = new TreeNode(max);

        //三，切割数组
        int[] leftTree = Arrays.copyOfRange(nums, 0, maxIndex);
        int[] rightTree = new int[]{};
        if (maxIndex + 1 < nums.length) {
            rightTree = Arrays.copyOfRange(nums, maxIndex + 1, nums.length);
        }


        //四、左子数组继续切割
        node.left = constructMaximumBinaryTree(leftTree);
        node.right = constructMaximumBinaryTree(rightTree);


        return node;

    }


    /**
     * 617. 合并二叉树
     * 简单
     * 1.3K
     * 相关企业
     * 给你两棵二叉树： root1 和 root2 。
     * 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
     * 返回合并后的二叉树。
     * 注意: 合并过程必须从两个树的根节点开始。
     *
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        //判断第一课树得节点是否为空
        if (root1 == null) {
            return root2;
        }

        //判断第二课树得节点是否为空
        if (root2 == null) {
            return root1;
        }

        TreeNode root = new TreeNode(root1.val + root2.val);

        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);

        return root;
    }


    /**
     * 700. 二叉搜索树中的搜索
     * 简单
     * 444
     * 相关企业
     * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
     * 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
     *
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || val == root.val) {
            return root;
        }


        if (val < root.val) {
            return searchBST(root.left, val);
        }


        if (val > root.val) {
            return searchBST(root.right, val);
        }


        return null;
    }


    /**
     * 98. 验证二叉搜索树
     * 中等
     * 2.2K
     * 相关企业
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     * 有效 二叉搜索树定义如下：
     * 节点的左子树只包含 小于 当前节点的数。
     * 节点的右子树只包含 大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     *
     * @param root
     * @return
     */
    //private long min = Long.MIN_VALUE;
    private TreeNode pre = null;

    public boolean isValidBST(TreeNode root) {
        //如果
        if (root == null) {
            return true;
        }

        //左
        boolean leftFlag = isValidBST(root.left);

        if (pre != null && pre.val >= root.val) {
            return false;
        } else {
            pre = root;
        }

        //右
        boolean rightFlag = isValidBST(root.right);
        return leftFlag && rightFlag;


    }


    /**
     * 530. 二叉搜索树的最小绝对差
     * 简单
     * 515
     * 相关企业
     * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
     * <p>
     * 差值是一个正数，其数值等于两值之差的绝对值。
     *
     * @param root
     * @return
     */

    public int getMinimumDifference(TreeNode root) {
        //思路一：超时
        //Stack<TreeNode> stack = new Stack<>();
        //ArrayList<Integer> list = new ArrayList<>();
        //TreeNode curr = root;
        //
        //while (curr != null || !stack.isEmpty()) {
        //
        //    if (curr != null) {
        //        stack.push(curr);
        //        curr = root.left;
        //    } else {
        //        TreeNode node = stack.pop();
        //        list.add(node.val);
        //        curr = node.right;
        //    }
        //}
        //
        //int min = Integer.MAX_VALUE;
        //
        //for (int i = 1; i  < list.size(); i++) {
        //    if (Math.abs(list.get(i) - list.get(i - 1)) < min) {
        //        min = Math.abs(list.get(i) - list.get(i - 1));
        //    }
        //}
        //
        //return min;
        getMinimun(root);
        return min;

    }

    private TreeNode preNode = null;
    private int min = Integer.MAX_VALUE;

    public void getMinimun(TreeNode node) {


        if (node == null) {
            return;
        }

        getMinimun(node.left);        //左

        if (preNode != null) {
            min = Math.min(min, node.val - preNode.val);
        }
        preNode = node;


        getMinimun(node.right);     //右
    }


    /**
     * 501. 二叉搜索树中的众数
     * 简单
     * 707
     * 相关企业
     * 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
     * 如果树中有不止一个众数，可以按 任意顺序 返回。
     * 假定 BST 满足如下定义：
     * <p>
     * <p>
     * 结点左子树中所含节点的值 小于等于 当前节点的值
     * 结点右子树中所含节点的值 大于等于 当前节点的值
     * 左子树和右子树都是二叉搜索树
     *
     * @param root
     * @return
     */
    public int[] findMode(TreeNode root) {
        if (root.left == null && root.right == null) {
            return new int[]{root.val};
        }
        ArrayList<Integer> res = new ArrayList<>();

        find(root, res);

        int[] resInt = new int[res.size()];
        int i = 0;
        for (int num : res) {
            resInt[i++] = num;
        }
        return resInt;

    }

    //private TreeNode pre = null;
    private int count = 0;
    private int max = 0;

    public void find(TreeNode node, ArrayList<Integer> res) {
        if (node == null) {
            return;
        }


        //左
        find(node.left, res);

        if (pre == null) {
            count = 1;
        } else if (pre.val == node.val) {
            count++;
        } else if (pre.val != node.val) {
            count = 1;
        }

        //切换节点
        pre = node;

        if (count == max) {
            res.add(node.val);
        }

        if (count > max) {
            res.clear();
            max = count;
            res.add(node.val);
        }

        //右
        find(node.right, res);

    }


    /**
     * 236. 二叉树的最近公共祖先
     * 中等
     * 2.5K
     * 相关企业
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //普通二叉树、平衡二叉树，都适用
        //if (root == null || root == p || root == q) {
        //    return root;
        //}
        //
        //TreeNode left = lowestCommonAncestor(root.left, p, q);
        //
        //TreeNode right = lowestCommonAncestor(root.right, p , q);
        //
        ////如果
        //if (left != null && right != null) {
        //    return root;
        //}
        //
        //if (left != null && right == null) {
        //    return left;
        //}
        //
        //if (right != null && left == null) {
        //    return right;
        //}
        //
        //return null;

        //平衡二叉树
        if (root == null) {
            return root;
        }

        //这里的思路就是，如果都大于，那么这俩节点一定左子树，如果都小于，则一定在又子树
        //而如果不符合这俩条件，那么就说明，这俩节点分布在root的左右子树，那么他们的共同祖先节点就肯定是root
        //而如果是进了这俩if，如果先循环遍历到了其中国的一个节点，那么该节点就肯定是这俩个节点的共同祖先节点
        if (root.val > p.val && root.val > q.val) {
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            if (left != null) {
                return left;
            }
        }


        if (root.val < p.val && root.val < q.val) {
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (right != null) {
                return right;
            }
        }


        return root;


    }


    /**
     * 701. 二叉搜索树中的插入操作
     * 中等
     * 536
     * 相关企业
     * 给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
     * <p>
     * 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
     *
     * @param root
     * @param val
     * @return
     */
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
            return root;
        }

        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }

        if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }


    /**
     * 450. 删除二叉搜索树中的节点
     * 中等
     * 1.3K
     * 相关企业
     * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
     * 一般来说，删除节点可分为两个步骤：
     * <p>
     * 首先找到需要删除的节点；
     * 如果找到了，删除它。
     *
     * @param root
     * @param key
     * @return
     */


    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return root;
        }

        if (root.val > key) {

            root.left = deleteNode(root.left, key);
        }

        if (root.val < key) {

            root.right = deleteNode(root.right, key);

        }

        if (root.val == key) {
            if (root.left == null && root.right == null) {
                return null;
            } else if (root.left != null && root.right == null) {
                return root.left;
            } else if (root.left == null && root.right != null) {
                return root.right;
            } else {
                TreeNode curr = root.right;     //右树
                while (curr.left != null) {
                    curr = curr.left;
                }
                //把左树放在右树的最左边
                curr.left = root.left;
                return root.right;
            }
        }

        return root;        //返回当前节点
    }


    /**
     * 669. 修剪二叉搜索树
     * 中等
     * 877
     * 相关企业
     * 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
     * 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
     *
     * @param root
     * @param low
     * @param high
     * @return
     */
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return root;
        }

        //不符合条件继续寻找
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }

        if (root.val > high) {
            return trimBST(root.left, low, high);
        }

        //符合条件，正常递归
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);


        return root;

    }


    /**
     * 108. 将有序数组转换为二叉搜索树
     * 简单
     * 1.4K
     * 相关企业
     * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
     * <p>
     * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
     *
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        if (nums.length == 1) {
            return new TreeNode(nums[0]);
        }

        //切割左右数组
        int index = nums.length / 2;
        TreeNode root = new TreeNode(nums[index]);
        int[] letfTree = Arrays.copyOfRange(nums, 0, index);
        int[] rightTree = new int[]{};
        if (index + 1 < nums.length) {
            rightTree = Arrays.copyOfRange(nums, index + 1, nums.length);
        }

        root.left = sortedArrayToBST(letfTree);
        root.right = sortedArrayToBST(rightTree);

        return root;
    }


    /**
     * 538. 把二叉搜索树转换为累加树
     * 中等
     * 952
     * 相关企业
     * 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
     * 提醒一下，二叉搜索树满足下列约束条件：
     * <p>
     * 节点的左子树仅包含键 小于 节点键的节点。
     * 节点的右子树仅包含键 大于 节点键的节点。
     * 左右子树也必须是二叉搜索树。
     * 注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
     *
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {

        addBST(root);
        return root;
    }


    private int sum = 0;
    public void addBST(TreeNode node) {

        if (node == null) {
            return;
        }
        //右

        addBST(node.right);

        //中
        node.val += sum;
        sum = node.val;
        //左
        addBST(node.left);

    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        //TreeNode left = new TreeNode();
        TreeNode right = new TreeNode(2);
        //root.left = left;
        root.right = right;

        Solution so = new Solution();
        so.findMode(root);
    }

}
